The present invention relates to a device for compressing a list of destination addresses of a multicast message, and a method for compressing a list of destination addresses of a multicast message, a router of a communications network wherein such a device for compressing is included, and a host of a communications network wherein such a device for compressing is included.
Multicasting is the transmission of one and the same message to a set of destination hosts. Multicasting on the Internet allows to send IP (Internet Protocol) datagrams to every host who cares to listen without the necessity to send the IP datagrams individually to each destination. Broadcasting radio stations on the Internet, audio- or video-conferencing, publishing a newsletter, attending meetings without leaving the office, seeing lectures from professors, and many other applications become realistic without excessive bandwidth occupancy through multicasting. In a host-group implementation of IP multicasting, each multicasted IP packet carries an IP multicast address, which is a single IP destination address that identifies all group members of the multicast session. The membership of the host group is dynamic which means that destination hosts may join and leave the group at any time. The forwarding of IP multicast datagrams is handled by so called multicast routers which are IP routers that have the responsibility to forward IP multicast datagrams to all networks that have members of the destination host group. An overview of multicast protocols for a host implementation of IP multicasting, such as XTP (Xpress Transfer Protocol), ST-II (Experimental Internet Stream Protocol Version 2), MTP (Multicast Transport Protocol), is given in rfc1458 entitled ‘Requirements for Multicast Protocols’. This IETF (Internet Engineering Task Force) submission is published on the Internet. The scalability of host implementation of IP multicasting for many groups however is a problem. In particular, the IP backbone network may suffer from scalability problems since the number of groups whose states have to be maintained there can be huge in case a separate multicast address has to be allocated to every small group of hosts attending for example an audio-conference or a video-conference. A connectionless implementation of IP multicasting, such as described in the Internet Draft entitled ‘Connectionless Multicast’, does not have the scalability problem of host implementations of IP multicasting since no state per multicast group is created in the IP routers. The latter Internet Draft proposes a multicast mechanism wherein each IP packet carries a list of all IP addresses of the multicast session members. In each router, the next hop for each destination in the list is determined by consulting the routing tables, and for every distinct next hop, a new IP header is constructed. This new IP header only contains a list of destinations for which that next hop is on the shortest path to the destinations. The main advantages of connectionless multicasting are that no multicast address allocation is required and routers do not have to maintain a state per session. Connectionless multicasting however requires each packet to contain all remaining destinations. Since the list of destination addresses might be long, connectionless multicasting may significantly increase the overhead and consequently reduce the effective throughput through the Internet.
The usefulness of a method and equipment for compressing the list of destination addresses in connectionless multicasted IP packets is expressed in paragraph 6 of the Internet Draft but a preferred implementation of the compression technique to be applied is not described therein. The authors of the Internet Draft already suggested that the compression method preferably should be based on detection of a common prefix. A common prefix based compression method for IP destination addresses is known for example from the article ‘Fast Address Lookup for Internet Routers’ from the authors Stefan Nilsson and Gunnar Karlsson. Therein, a method for compressing the information held by the routing table of IP routers is described. This compression technique replaces IP addresses with a prefix and skip value, the skip value representing the number of bits that can be skipped during a search operation. If in the list of destination addresses of a multicast message, destination addresses having a common prefix would be replaced with a compound destination address consisting of the common prefix and a skip number indicative for the number of irrelevant bits, every host whose address starts with the common prefix would receive the multicasted message, whether this host forms part of the original list of destinations or not. Thus, only sets of destination addresses having a common prefix and containing all possible suffixes could be compressed this way for multicast purposes. This known compression technique based on common prefixes would therefore be applicable very sparsely and, as a consequence, cannot significantly reduce the aggregate overhead generated for multicast traffic in the Internet.